Current Issue : April - June Volume : 2014 Issue Number : 2 Articles : 4 Articles
We develop an efficient multicore algorithm, PMS6MC, for the (l, d)-motif\r\ndiscovery problem in which we are to find all strings of length l that appear in every string\r\nof a given set of strings with at most d mismatches. PMS6MC is based on PMS6, which\r\nis currently the fastest single-core algorithm for motif discovery in large instances. The\r\nspeedup, relative to PMS6, attained by our multicore algorithm ranges from a high of 6.62\r\nfor the (17,6) challenging instances to a low of 2.75 for the (13,4) challenging instances on\r\nan Intel 6-core system. We estimate that PMS6MC is 2 to 4 times faster than other parallel\r\nalgorithms for motif search on large instances....
We address the numerical solution of Lyapunov, algebraic and differential\r\nRiccati equations, via the matrix sign function, on platforms equipped with general-purpose\r\nmulticore processors and, optionally, one or more graphics processing units (GPUs).\r\nIn particular, we review the solvers for these equations, as well as the underlying\r\nmethods, analyze their concurrency and scalability and provide details on their parallel\r\nimplementation. Our experimental results show that this class of hardware provides sufficient\r\ncomputational power to tackle large-scale problems, which only a few years ago would have\r\nrequired a cluster of computers....
This paper designs and evaluates a variant of CoSaMP algorithm, for recovering\r\nthe sparse signal s from the compressive measurement v (Uw s) given a fixed lowrank\r\nsubspace spanned by U. Instead of firstly recovering the full vector\r\nthen separating the sparse part from the structured dense part, the proposed algorithm\r\ndirectly works on the compressive measurement to do the separation. We investigate the\r\nperformance of the algorithm on both simulated data and video compressive sensing. The\r\nresults show that for a fixed low-rank subspace and truly sparse signal the proposed\r\nalgorithm could successfully recover the signal only from a few compressive sensing (CS)\r\nmeasurements, and it performs better than ordinary CoSaMP when the sparse signal is\r\ncorrupted by additional Gaussian noise....
The stable matching problem (also known as the stable marriage problem) is\r\na well-known problem of matching men to women, so that no man and woman, who are\r\nnot married to each other, both prefer each other. Such a problem has a wide variety of\r\npractical applications, ranging from matching resident doctors to hospitals, to matching\r\nstudents to schools or, more generally, to any two-sided market. In the classical stable\r\nmarriage problem, both men and women express a strict preference order over the members\r\nof the other sex, in a qualitative way. Here, we consider stable marriage problems with\r\nweighted preferences: each man (resp., woman) provides a score for each woman (resp.,\r\nman). Such problems are more expressive than the classical stable marriage problems.\r\nMoreover, in some real-life situations, it is more natural to express scores (to model, for\r\nexample, profits or costs) rather than a qualitative preference ordering. In this context, we\r\ndefine new notions of stability and optimality, and we provide algorithms to find marriages\r\nthat are stable and/or optimal according to these notions. While expressivity greatly increases\r\nby adopting weighted preferences, we show that, in most cases, the desired solutions can be\r\nfound by adapting existing algorithms for the classical stable marriage problem. We also\r\nconsider the manipulability properties of the procedures that return such stable marriages.\r\nWhile we know that all procedures are manipulable by modifying the preference lists or\r\nby truncating them, here, we consider if manipulation can occur also by just modifying the\r\nweights while preserving the ordering and avoiding truncation. It turns out that, by adding weights, in some cases, we may increase the possibility of manipulating, and this cannot be\r\navoided by any reasonable restriction on the weights....
Loading....